# -*- coding:utf-8 -*-
'''
输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。

递归大法好
'''
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
class Solution:
    def __init__(self):
        self.stack = []
        self.res = []


    # 返回二维列表，内部每个列表表示找到的路径
    def FindPath(self, root, expectNumber):
        # write code here
        if root:
            self.stack.append(root.val)
            if not root.left and not root.right:
                if sum(self.stack) == expectNumber:
                    self.res.append(self.stack)
                    self.stack = self.stack[0:1]
                else:
                    self.stack.pop()
            else:
                self.FindPath(root.left,expectNumber)
                self.FindPath(root.right,expectNumber)
        return self.res

a10 = TreeNode(10)
a5 = TreeNode(5)
a12 = TreeNode(12)
a4 = TreeNode(4)
a7 = TreeNode(7)
a10.left = a5
a10.right = a12
a5.left = a4
a5.right = a7

s = Solution()
print(s.FindPath(a10,22))
